﻿#include <iostream>
#include <vector>

#include <climits>
using namespace std;
// 动态规划 54
//int coinChange(vector<int>& coins, int amount) 
//{
//	int n = coins.size();
//	vector<vector<int> > dp(n+1, vector<int>(amount + 1)); // 建表
//	// 初始化
//	for (int j = 1; j <= amount; j++)
//		dp[0][j] = INT_MAX;
//
//	for (int i = 1; i <= n; i++)
//		for (int j = 0; j <= amount; j++)
//		{
//			dp[i][j] = dp[i - 1][j];
//			if (j >= coins[i - 1])
//				dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]]) + 1;
//		}
//	return dp[n][amount] >= INT_MAX ? -1 : dp[n][amount];
//}

// 优化
int coinChange(vector<int>& coins, int amount)
{
	int n = coins.size();
	vector<int> dp(amount + 1, INT_MAX); // 建表
	// 初始化
	dp[0] = 0;
	for (int i = 1; i <= n; i++)
		for (int j = coins[i - 1]; j <= amount; j++)
			dp[j] = min(dp[j], dp[j - coins[i - 1]] + 1);
	return dp[amount] >= INT_MAX ? -1 : dp[amount];
}

int main()
{
	vector<int> v = { 1,2,5 };
	cout << coinChange(v, 11) << endl;

	return 0;
}